package com.hy.treeNode3;

import com.hy.treeNode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PathSum {


    /**
     * 113. 路径总和
     * 力扣题目链接
     *
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:  给定如下二叉树，以及目标和 sum = 22，
     *
     * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
     *
     * 思路
     * 这道题我们要遍历从根节点到叶子节点的的路径看看总和是不是目标和。
     * @param root
     * @param targetSum
     * @return
     */

    // 0113.路径总和-ii  解法1：
    public List<List<Integer>> pathSum(TreeNode root ,int targetSum){
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (root == null){
            return res;
        }
        preorderdfs(root,targetSum,res,path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetSum,List<List<Integer>> res, List<Integer> path){
        path.add(root.val);
        // 如果 遇到 叶子节点(左右子树为空) 则进行 路径数据添加
        if (root.left == null && root.right == null){
            // 找到了和为 targetsum 的路径
            if (targetSum - root.val == 0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if (root.left != null){
            // 递归
            preorderdfs(root.left,targetSum - root.val,res,path);
            // 回溯
            path.remove(path.size() -1);
        }
        if (root.right != null){
            preorderdfs(root.right, targetSum - root.val, res, path);
            // 回溯
            path.remove(path.size() - 1);
        }
    }

    // 0113.路径总和-ii  解法1：
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum2(TreeNode root,int targetSum){
        travesal(root,targetSum);
        return res;
    }
    public void travesal(TreeNode root , int targetSum){
        if (root == null){
            return;
        }
        path.offer(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0){
            res.add(new LinkedList<>(path));
        }
        travesal(root.left,targetSum);
        travesal(root.right,targetSum);
        // 回溯
        path.removeLast();
    }




    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        PathSum hasPathSum = new PathSum();

        System.out.println("路径总和-i: "+hasPathSum.pathSum(root,18));
        System.out.println("路径总和-ii: "+hasPathSum.pathSum2(root,18));

    }
}
